The predominant approach currently used in the design of logic circuits requires synchonous circuit operation (i.e., operation synchronized with a clock signal). The vast majority of sequential circuits currently implemented with Very Large Scale Integrated (VLSI) circuit technology are designed in accordance with synchronous design theory. However, use of synchronous design in VLSI circuits has several disadvantages.
One assumption that avoids race conditions (i.e., internal transistions in which at least two internal state variables change simultaneously) with synchronous circuit design is that all signals must finish propagating before the next sampling clock edge. This simplifying design assumption affects the speed of a synchronous circuit which is thereby governed by the slowest functional block. Clock lines in synchronous VLSI circuitry thus must be distributed so that clock skew between logic sections due to propagation of the clock signal is within an allowable limit to avoid having race conditions introduced by this skew. In order to minimize skew and also overcome the essential hazards inherent in most synchronous flip flops, clock drivers must be sized to have very fast rise and fall times. Most of the instantaneous power drawn by a synchronous VLSI circuit occurs at the clock edges due to the current drawn by the large clock drivers and the nodes set in motion by the clock edge. A major design consideration for VLSI chips is to size the power busses to account for this peak current draw.
Asynchronous design is a solution to these and to other problems with synchronous circuit design. Each section of an asynchronous circuit operates independently at each such section's inherent maximum rate of speed, and thus the overall system speed is not governed by the slowest section of the logic. No synchronizing clock needs to be distributed, thus avoiding races introduced due to clock skew and the design effort to distribute the clock signal properly. Power requirements are also reduced since no clock drivers are required and the logical nodes are not all triggered to undergo simultaneous transitions.
Pass transistor networked have been used to form combinational logic structures in MOS VLSI logic circuits. Early circuits using pass transistors were designed to reduce power, delay and area for MOS logic circuits. Pass transistors were used in NMOS designs to steer and block logic signals in flip flops, latches and selector circuits, as well as in some combinational circuits such as carry chains. Formal techniques for the design of NMOS pass transistor circuits, and portions of several NMOS VLSI custom chip designs, are described in the following U.S. Patents issued to S. R. Whitaker, one of the present inventors: U.S. Pat. No. 4,541,067, issued Sept. 10, 1985; U.S. Pat. No. 4,566,064, issued Jan. 21, 1986; and U.S. Pat. No. 4,622,648, issued Nov. 11, 1986.
However, the use of pass transistors in sequential circuits has been limited to the combinational next state forming logic in synchronous sequential machines. Asynchronous sequential pass transistor circuits have not been developed.
To simplify the description of the invention, it will be helpful to summarize relevant conventional pass transistor circuit terminology.
The logical function of a pass transistor is described in Table 1:
TABLE 1 ______________________________________ Control Input Output ______________________________________ 0 0 -- 0 1 -- 1 0 0 1 1 1 ______________________________________
When the "control" terminal of a pass transistor is high, the logic level presented at the input is passed to the output. When the control terminal is low, the output is in a floating or high impedance state. The simplest model of the pass gate would be a switch closed under the appropriate control condition and open under the opposite control condition.
A single NMOS or PMOS transistor can be used to implement the pass transistor function, although two transistors (an NMOS and PMOS transistor) are at times used to implement a single pass gate. A MOS transistor is bidirectional and there is not physical distinction between the source and drain terminals. When a MOS transistor is used to implement a pass transistor function, the terms input and output must be defined by the circuitry connected to the drain and source terminals of the MOSFET. The input to a pass transistor is the terminal connected to the source of logic state. The output of a pass transistor applies the logic state present on the pass transistor's input to the input of another logic gate.
The logical function of a single pass transistor will be represented schematically in this Specification by the symbol in FIG. 1. When PMOS transistors are used in conjunction with NMOS transistors, a letter ("p" or "n") designating the transistor as PMOS (p) or NMOS (n) will be added to the diagram. The "(p)(n)" notation also clarifies the logic state necessary on the control port to cause the logic level on the input to be passed to the output.
Combinational logic networks are formed by joining the outputs and inputs of sets of pass transistors. Outputs for pass transistors can be joined together, if all paths to the output that may be simultaneously enabled will pass the same logic state (to avoid conflict). A general combinational pass transistor network is shown in FIG. 2.
A set of control variables, C, drives the control terminals of a pass transistor network. Given a set of n boolean inputs, I, such that EQU I=x.sub.1, x.sub.2, . . . , x.sub.n
then, EQU C [x.sub.1, x.sub.1, x.sub.2, x.sub.2, . . . , x.sub.n, x.sub.n ].
A set of pass variable, V, drive the inputs of the pass network and are passed to the output of the pass network, so that: EQU V [x.sub.1, x.sub.1, x.sub.2, x.sub.2, . . . , x.sub.n, x.sub.n, O, 1].
A pass network can be represented as shown in FIG. 3. Each section labeled P.sub.i consists of a series of pass transistors. P.sub.i is a product term containing elements of C as literals. Each literal represents an input variable which drives the control gate of a series pass transistor in P.sub.i.
The control function of a pass network element is the product term describing P.sub.i in which each literal of P.sub.i must be asserted to pass the input variable V.sub.i to the output. The notation used to describe the output, F, of the pass network shown in FIG. 3 is of the following form. ##EQU1##
When all the literals in P.sub.i are asserted then the input variable, V.sub.i, is passed to the output, F. If V.sub.i is the pass variable passed by P.sub.i, then P.sub.i (V.sub.i) denotes the pass implicant.
To simplify description of the inventive pass transistor asynchronous sequential circuit design method, it will also be helpful to summarize the relevant conventional asynchronous sequential circuit terminology.
An asynchronous sequential circuit is defined in terms of input, internal and output states. The input states are applied from external sources, the internal state is contained within the required memory function of the circuit and the output state is presented to the external environment. The activity of an asynchronous sequential circuit is often defined in terms of a flow table, such as Table 2 set forth below:
TABLE 2 ______________________________________ I.sub.1 I.sub.2 I.sub.3 I.sub.4 y.sub.1 y.sub.2 y.sub.3 ______________________________________ A A B D -- 0 0 0 B A B C B 0 1 1 C A C C B 1 1 1 D D C D -- 1 0 0 ______________________________________
The internal states are encoded with state variables, y.sub.i (so that, for example, in Table 2, internal state A is the internal state in which y.sub.1 =0, and y.sub.3 =0). The input states are noted as I.sub.i. The entries of the flow table columns headed by input state I.sub.i are the next state variables, Y.sub.i, and the output state variables, Z.sub.i. Although the output states Z.sub.i are omitted from the entries of Table 2, it should be understood that each entry in the first four columns of Table 2 corresponds not only to an input state (I.sub.i), a present internal state (A, B, C, or D), and a next internal state (A, B, C, or D), but also to one of output state variables Z.sub.i.
The circuit's "present state" is a set of boolean values representing the current values of the internal state variables. For a circuit with n state variables, the set of present state variables will be represented by y=[y.sub.1, y.sub.2, . . . y.sub.n ]. For a circuit with four state variables, the set of state variables will be represented by y=[y.sub.1, y.sub.2, y.sub.3, y.sub.4 ]. The internal state would be represented by the boolean value of each state variable. The internal state might be 0110 implying y.sub.1 =0 y.sub.2 =1 y.sub.3 =1 y.sub.4 =0.
The circuit's "next state" is a set of boolean values representing the new state that the internal state variables will assume under a given condition of the inputs. For a circuit with n state variables, the set of next states will be represented by Y=[Y.sub.1, Y.sub.2, . . . Y.sub.n ].
The "total circuit state" of a sequential circuit is the internal state plus the input state. If [S.sub.i ] represents the set of present state variables and [I.sub.p ] represents the set of input states then the total circuit state is represented by (S.sub.i, I.sub.p). For example, (A, I.sub.1) denotes the stable total circuit state in the first column of Table 2.
The design equations of a sequential circuit consist of equations for the next state variables, Y.sub.i, and the output state variables, Z.sub.i. These equations are a function of the internal state variables.
A sequential circuit is in a "stable" state when the next state and the present state are equal; all other specified states are "unstable." The upper left entry in Table 2 thus represents a stable state. A sequential circuit will remain in a stable state until another input is applied to the circuit to cause a transition to a new state. If unstable state S.sub.j transitions to stable state S.sub.i, (S.sub.j, S.sub.i) is called a "transition pair." The collection of the unstable states under a given input variable with the same next state entry together with the stable state are called a "k-set." In Table 2 under input I.sub.1, there are transition pairs (A,B) and (A,C) in K-set ABC.
A "transition path" is the sequence of potential states that the circuit could assume during a transition between unstable and stable states. For example, in Table 2, where A is encoded 000 and B is encoded 011 by state variables y.sub.1, y.sub.2, y.sub.3, the transition path between state B and state A would be 0--(i.e., all states where y.sub.1 =0). For the flow table shown in Table 2, the transition from state C to state D has two potential transition paths, 111 .fwdarw. 110 .fwdarw. 100 or 111 .fwdarw. 101 .fwdarw. 100. The specific path taken depends on circuit delays.
A "hazard" is a potentially incorrect transition of an output caused by differences in delay through combinational logic paths. Hazards can cause a circuit to malfunction even though a state assignment has been carefully chosen to avoid race conditions. There are several different hazards that may cause a malfunction, but collectively hazards resulting from delays through combinational logic are known as combinational hazards.
A "static" hazard occurs when a circuit output experiences a transition when that output should have remained constant. A "static one" hazard appears as a 1 .fwdarw. 0 .fwdarw. 1 transition on a node that should have remained a "1". A static zero hazard appears as a 0 .fwdarw. 1 .fwdarw. 0 transition on a node that should have remained a "0". Static hazards potentially exist when there are two paths to the output of a combinational logic network triggered by the same input change.
A "dynamic" hazard occurs when a variable experiences multiple transistions when only one transition should have occurred. Dynamic hazards occur when there are three or more paths to an output from a single input or it's inverse.
An "essential" hazard occurs because of excessive delay in circuit with two or more variables resulting in transition to an incorrect state as a result of an input change. An essential hazard can occur when a signal and it's inverse are both required by a sequential circuit. If the signals, due to delays, are at the same logic level for a sufficiently long time, the circuit can transition to an erroneous state regardless of whether the state assignment is critical race free.
"Races" occur whenever more than one internal state variable is excited at the same time. The fastest circuit operation can be achieved when all state variables that are to transition are excited simultaneously. This generates many race conditions.
A "critical race" occurs if the successor state is dependent on circuit delays. If transition paths lead to two distinct stable states depending on which state variable wins the race, the circuit will malfunction if the wrong stable state is reached. A race is "noncritical" if the successor state is not dependent on circuit delays. If both transition paths are through unstable states headed towards the same stable state, then the circuit will arrive safely at the correct stable state regardless of which state variable wins the noncritical race.
An important step in designing a sequential circuit is the binary coding of the circuit's internal states. This coding step is known as the "state assignment" operation, and the code for the internal states is known as the "state assignment." A "unit distance" state assignment allows only one state variable at a time to change between an unstable state and the stable state of a k-set. If all states between which a circuit may transition are logically adjacent, then all race conditions are eliminated. This is not always possible to achieve for a given flow table. A "one-hot-code" state assignment is a 1-out-of-n code where only a single state variable is asserted for each stable state. In a "single transition time" (SST) state assignment, the state variables that are to change state are all simultaneously excited at the start of the transition.
There are several STT state assignments which are critical race free. These were developed by Tracey in "Internal State Assignments for Asynchronous Sequential Machines," IEEE Trans. on Electronic Computers, V. EC-15, No. 4, pp. 551-560 (August 1966), Liu in "A State Variable Assignment Method for Asynchronous Sequential Switching Circuits," J.A.C.M., Vol. 10, pp. 209-216 (April 1963) and Tan in "State Assignments for Asynchronous Sequential Machines," IEEE Trans. on Computers, V. C-20, No. 4, pp. 382-391 (April 1971). A Tracey state assignment partitions each transition pair from all other transition pairs under each input. A Liu assignment partitions k-sets under each input. A Tan assignment is a Liu assignment with the provision that only one state variable is required to partition a transition path (k-set).
Until the present invention, it was not known how to efficiently design and construct asynchronous sequential circuits employing pass transistor networks. The inventive method is capable of designing a pass transistor asynchronous sequential circuit to implement any of a broad class of logical functions using minimal or near minimal hardware. The several embodiments of the inventive method disclosed herein are easier to use than conventional asynchronous sequential circuit design techniques. Pass transistor implementations that result from performance of the invention have greatly reduced transistor counts and the design equations are related directly to the structure of the flow table. This relationship between the flow table and the circuit is evident in both the design equations and many of the logical implementations. Standard state assignments are employed in performing the invention. Partition algebra is applied to produce design equations which are written by inspection. The invention results in critical race free circuits exhibiting increased freedom from essential and functional hazards associated with inputs.